package algorithm.array;

import java.util.Arrays;

/**
 * Leetcode: https://leetcode.com/problems/search-a-2d-matrix-ii/
 * Medium
 *
 * 搜索二维矩阵
 * Created by yzy on 2021-03-03 19:44
 */
public class SearchMatrix {


    /**
     * 折线搜索，和每一行的最后一个比较，如果大于这个数，那么就大于该行所有的数，直接进入下一行。
     * 找到对应行以后，再用二分法查找，就很快了
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        for(int[] subArr : matrix){
            if(subArr[0] <= target && subArr[subArr.length-1]>=target){
                // 由于子数组有序，那么直接使用二分查找
                if(Arrays.binarySearch(subArr,target) >= 0){
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 主方法：return search(matrix, target, 0,0);
     * 但是这样超时了,需要优化
     * @param matrix
     * @param target
     * @param x
     * @param y
     * @return
     */
    private boolean search(int[][] matrix, int target, int x, int y){
        if(x >= matrix.length || y>= matrix[0].length){
            return false;
        }
        int curr = matrix[x][y];
        if(curr > target){
            return false;
        }else if(curr == target){
            return true;
        }else{
            return search(matrix, target, x+1, y) || search(matrix, target, x, y+1);
        }
    }
}
